package com.hanxiaozhang.delayoperation.timewheel;

import java.util.concurrent.DelayQueue;
import java.util.concurrent.atomic.AtomicInteger;


/**
 * 功能描述: <br>
 * 〈层级时间轮〉
 * <p>
 * 它是一个存储定时任务的环形队列，底层使用数组实现，数组中的每个元素可以存放一个TimerTaskList对象。
 * TimerTaskList是环形双向链表，在其中的链表项TimerTaskEntry中封装了真正的定时任务TimerTask。
 * TimerTaskList使用expiration字段记录了整个TimerTaskList的超时时间。
 * TimerTaskEntry中的expirationMs字段记录了超时时间戳，timerTask字段指向了对应的TimerTask任务。
 * TimeTask中的delayMs记录了任务的延迟时间，timerTaskEntry字段记录了对应的TimerTaskEntry对象。
 * 这三个对象是TimingWheel实现的基础。
 * <p>
 * TimingWheel提供了层级时间轮的概念，第一层时间轮的时间跨度比较小，而第二层时间轮的时间跨度比较大。
 *
 * <p>
 * Hierarchical Timing Wheels
 * <p>
 * A simple timing wheel is a circular list of buckets of timer tasks. Let u be the time unit.
 * A timing wheel with size n has n buckets and can hold timer tasks in n * u time interval.
 * Each bucket holds timer tasks that fall into the corresponding time range. At the beginning,
 * the first bucket holds tasks for [0, u), the second bucket holds tasks for [u, 2u), …,
 * the n-th bucket for [u * (n -1), u * n). Every interval of time unit u, the timer ticks and
 * moved to the next bucket then expire all timer tasks in it. So, the timer never insert a task
 * into the bucket for the current time since it is already expired. The timer immediately runs
 * the expired task. The emptied bucket is then available for the next round, so if the current
 * bucket is for the time t, it becomes the bucket for [t + u * n, t + (n + 1) * u) after a tick.
 * A timing wheel has O(1) cost for insert/delete (start-timer/stop-timer) whereas priority queue
 * based timers, such as java.util.concurrent.DelayQueue and java.util.Timer, have O(rdbms n)
 * insert/delete cost.
 * <p>
 * A major drawback of a simple timing wheel is that it assumes that a timer request is within
 * the time interval of n * u parseFrom the current time. If a timer request is out of this interval,
 * it is an overflow. A hierarchical timing wheel deals with such overflows. It is a hierarchically
 * organized timing wheels. The lowest level has the finest time resolution. As moving up the
 * hierarchy, time resolutions become coarser. If the resolution of a wheel at one level is u and
 * the size is n, the resolution of the next level should be n * u. At each level overflows are
 * delegated to the wheel in one level higher. When the wheel in the higher level ticks, it reinsert
 * timer tasks to the lower level. An overflow wheel can be created on-demand. When a bucket in an
 * overflow bucket expires, all tasks in it are reinserted into the timer recursively. The tasks
 * are then moved to the finer grain wheels or be executed. The insert (start-timer) cost is O(m)
 * where m is the number of wheels, which is usually very small compared to the number of requests
 * in the system, and the delete (stop-timer) cost is still O(1).
 * <p>
 * Example
 * Let's say that u is 1 and n is 3. If the start time is c,
 * then the buckets at different levels are:
 * <p>
 * level    buckets
 * 1        [c,c]   [c+1,c+1]  [c+2,c+2]
 * 2        [c,c+2] [c+3,c+5]  [c+6,c+8]
 * 3        [c,c+8] [c+9,c+17] [c+18,c+26]
 * <p>
 * The bucket expiration is at the time of bucket beginning.
 * So at time = c+1, buckets [c,c], [c,c+2] and [c,c+8] are expired.
 * Level 1's clock moves to c+1, and [c+3,c+3] is created.
 * Level 2 and level3's clock stay at c since their clocks move in unit of 3 and 9, respectively.
 * So, no new buckets are created in level 2 and 3.
 * <p>
 * Note that bucket [c,c+2] in level 2 won't receive any task since that range is already covered in level 1.
 * The same is true for the bucket [c,c+8] in level 3 since its range is covered in level 2.
 * This is a bit wasteful, but simplifies the implementation.
 * <p>
 * 1        [c+1,c+1]  [c+2,c+2]  [c+3,c+3]
 * 2        [c,c+2]    [c+3,c+5]  [c+6,c+8]
 * 3        [c,c+8]    [c+9,c+17] [c+18,c+26]
 * <p>
 * At time = c+2, [c+1,c+1] is newly expired.
 * Level 1 moves to c+2, and [c+4,c+4] is created,
 * <p>
 * 1        [c+2,c+2]  [c+3,c+3]  [c+4,c+4]
 * 2        [c,c+2]    [c+3,c+5]  [c+6,c+8]
 * 3        [c,c+8]    [c+9,c+17] [c+18,c+18]
 * <p>
 * At time = c+3, [c+2,c+2] is newly expired.
 * Level 2 moves to c+3, and [c+5,c+5] and [c+9,c+11] are created.
 * Level 3 stay at c.
 * <p>
 * 1        [c+3,c+3]  [c+4,c+4]  [c+5,c+5]
 * 2        [c+3,c+5]  [c+6,c+8]  [c+9,c+11]
 * 3        [c,c+8]    [c+9,c+17] [c+8,c+11]
 * <p>
 * The hierarchical timing wheels works especially well when operations are completed before they time out.
 * Even when everything times out, it still has advantageous when there are many items in the timer.
 * Its insert cost (including reinsert) and delete cost are O(m) and O(1), respectively while priority
 * queue based timers takes O(rdbms N) for both insert and delete where N is the number of items in the queue.
 * <p>
 * This class is not thread-safe. There should not be any add calls while advanceClock is executing.
 * It is caller's responsibility to enforce it. Simultaneous add calls are thread-safe.
 *
 *
 * @Author:hanxinghua
 * @Date: 2024/2/26
 */
class TimingWheel {

    /**
     * 当前时间轮中一个时间格表示的时间跨度
     */
    private final Long tickMs;

    /**
     * 当前时间轮的格数，也是buckets数组的大小
     */
    private final Integer wheelSize;

    /**
     * 当前时间轮的创建时间
     */
    private final Long startMs;

    /**
     * 全局唯一的任务计数器
     * 各层级时间轮中任务的总数
     */
    private final AtomicInteger taskCounter;

    /**
     * 全局唯一的任务队列
     * 整个层级时间轮共用的一个任务队列
     */
    private final DelayQueue<TimerTaskList> queue;


    /**
     * 当前时间轮的时间跨度，即tickMsWheelSize。
     * 当前时间轮只能处理时间范围在currentTime ~ currentTime+tickMsWheelSize之间的定时任务，
     * 超过这个范围，则需要将任务添加到上层时间轮中。
     */
    private final Long interval;


    /**
     * buckets数组
     * 每一个项都对应时间轮中的一个时间格，用于保存TimerTaskList的数组。
     */
    private final TimerTaskList[] buckets;

    /**
     * 时间轮的指针，将整个时间轮划分为到期部分和未到期部分。
     * 在初始化时，currentTime被修剪成tickMs的倍数，近似等于创建时间，
     * 但并不是严格的创建时间。
     */
    private Long currentTime;


    /**
     * 上层时间轮的引用
     * <p>
     * overflowWheel可能由两个并发线程通过add()进行更新和读取。
     * 因此，volatile使用DCL机制
     */
    // overflowWheel can potentially be updated and read by two concurrent threads through add().
    // Therefore, it needs to be volatile due to the issue of Double-Checked Locking pattern with JVM
    private volatile TimingWheel overflowWheel;

    public TimingWheel(Long tickMs, Integer wheelSize, Long startMs, AtomicInteger taskCounter, DelayQueue<TimerTaskList> queue) {

        this.tickMs = tickMs;
        this.wheelSize = wheelSize;
        this.startMs = startMs;
        this.taskCounter = taskCounter;
        this.queue = queue;

        this.interval = tickMs * wheelSize;
        this.buckets = new TimerTaskList[wheelSize];
        for (int i = 0; i < buckets.length; i++) {
            this.buckets[i] = new TimerTaskList(taskCounter);
        }
        // 四舍五入为tickMs的倍数
        this.currentTime = startMs - (startMs % tickMs);
    }


    /**
     * 创建上层时间轮
     */
    private void addOverflowWheel() {
        synchronized (this) {
            if (overflowWheel == null) {
                // 此时入参tickMs，传入的是tickMs
                overflowWheel = new TimingWheel(interval, wheelSize, currentTime, taskCounter, queue);
            }
        }
    }


    /**
     * 向时间轮中添加定时任务，同时也会检测待添加的任务是否已经到期
     *
     * 知识点：
     * 1.复用时间轮
     * 2.多层时间轮
     *
     * @param timerTaskEntry
     * @return
     */
    boolean add(TimerTaskEntry timerTaskEntry) {
        Long expiration = timerTaskEntry.getExpirationMs();
        // 任务已经被取消  Cancelled
        if (timerTaskEntry.cancelled()) {
            return false;
            // 任务已经到期  Already expired
        } else if (expiration < currentTime + tickMs) {
            return false;
            // 任务在当前时间轮的跨度范围内  ->  时间轮复用
        } else if (expiration < currentTime + interval) {

            // 整个时间轮表示的时间跨度是不变的，随着表针currentTime的后移，当前时间轮能处理时间段也在不断后移，
            // 新来的TimerTaskEntry会复用原来已经清理过的TimerTaskList(bucket)。
            // 此时需要重置TimerTaskList(bucket)的到期时间，并将bucket重新添加到DelayQueue中。

            // Put in its own bucket
            long virtualId = expiration / tickMs;
            TimerTaskList bucket = buckets[(int) (virtualId % (long) wheelSize)];
            bucket.add(timerTaskEntry);

            // 设置 bucket 的到期时间 -> 如果设置过期时间成功，证明是bucket首次用到，需要添加到queue中。
            if (bucket.setExpiration(virtualId * tickMs)) {

                // bucket需要重新添加，因为它是一个过期的 bucket
                // The bucket needs to be enqueued because it was an expired bucket
                // We only need to enqueue the bucket when its expiration time has changed, i.e. the wheel has advanced
                // and the previous buckets gets reused; further calls to set the expiration within the same wheel cycle
                // will pass in the same value and hence return false, thus the bucket with the same expiration will not
                // be enqueued multiple times.
                queue.offer(bucket);
            }
            return true;
            // 超出了当前时间轮的时间跨度范围，则将任务添加到上层时间轮中处理
        } else {
            if (overflowWheel == null) {
                // 创建上层时间轮
                addOverflowWheel();
            }
            return overflowWheel.add(timerTaskEntry);
        }
    }


    /**
     * 尝试推进当前时间轮的表针currentTime，同时也会尝试推进上层的时间轮的表针。
     * 随着当前时间轮的表针不断被推进，上层时间轮的表针也早晚会被推进成功。
     *
     * @param timeMs
     */
    void advanceClock(Long timeMs) {

        // 尝试移动表针currentTime，推进可能不止一格
        if (timeMs >= currentTime + tickMs) {
            // 计算时间轮的指针，timeMs根据tickMs取整
            currentTime = timeMs - (timeMs % tickMs);
            // 尝试推进上层时间轮的表针
            if (overflowWheel != null) {
                overflowWheel.advanceClock(currentTime);
            }
        }
    }
}
